The present invention relates generally to decoding algorithms, and more specifically, to the decoding algorithms used in a Huffman decoder.
Recently there has been a consistent rise in the demand for data transmission at low bit rates. In addition, there has been an increasing demand for reduction in data storage space. To cater to these requirements, various compression algorithms such as Huffman coding, discrete cosine transform (DCT), entropy coding and run-length coding have become popular compression techniques. Among the compression techniques mentioned above, a combination of Huffman and run-length coding is preferably used for compression. The preference is attributed to better compression ratios achieved by the above combination in which the data symbols are encoded as variable length Huffman code words. The lengths of the Huffman code words are in proportion to the estimated probabilities of occurrences of the data symbols in the data to be encoded. As a result, the data symbol that occurs frequently has a Huffman code word with a length shorter than the length of a Huffman code word that represents a data symbol with a low probability of occurrence, thereby achieving compression.
An essential component of Huffman encoding is the use of Huffman code books that include mapping of the data symbols and the Huffman code words that are used to represent the data symbols. Various encoding standards specify varying numbers of Huffman code books having varying content. For example, the Advanced Audio Coding (AAC) encoding standard has specified 12 Huffman code books, Moving Picture Experts Group-1 Audio Layer 3 (MP3) encoding standard has specified 34 Huffman code books, and Joint Photographic Experts Group (JPEG) has specified 2 Huffman code books. These Huffman code books are used by Huffman decoders, such as an AAC decoder, to decode an encoded bit stream.
FIG. 1 is a table 100 illustrating a part of Huffman code book 1 specified by the AAC standard. The table 100 includes a plurality of Huffman code words in hexadecimal format, a plurality of lengths associated with a binary representation of each of the Huffman code words, and a plurality of index values associated with each of the Huffman code words. The index values are used to calculate quantized spectral coefficients using an equation specified by the AAC standard.
FIG. 2 is a flow chart illustrating a conventional method for decoding an encoded input bit stream. At step 202, an input bit stream is received. At step 204, a first bit is extracted from the input bit stream. At step 206, a search is performed in the Huffman code book 1 illustrated in FIG. 1, for identifying a Huffman code word matching the first extracted bit. At step 208, a check is performed to determine whether a Huffman code word matching the first extracted bit is identified. If it is determined at step 208 that a Huffman code word has been identified during the search, step 210 is performed. At step 210, an index value associated with the identified Huffman code word is read from the table 100. Step 212 is performed after step 210. At step 212, the index value is used to calculate quantized spectral coefficients using an equation specified by the AAC standard.
However, at step 208, if it is determined that a Huffman code word has not been identified in the search, step 214 is performed. At step 214, a second bit is extracted from the input bit stream and then at step 216, the second bit is appended to the first bit. For example, if a first extracted bit has a binary value ‘1 ’ and a second extracted bit has a binary value ‘0 ’, the second extracted bit, i.e. ‘0 ’ will be appended to the first extracted bit ‘1 ’ resulting in a combination ‘10 ’. Thereafter, steps 206 onwards are repeated using ‘10 ’ as a search parameter. The above procedure of extracting a bit and appending it to the previously extracted bits is repeated until a matching Huffman code word is obtained.
The above method of decoding an input bit stream involves extraction of a single bit per decoding cycle. Thus, a large number of decoding cycles are required to decode the input bit stream. Large numbers of decoding cycles results in a high Million Instructions Per Second (MIPS) value. Further, large numbers of decoding cycles increases execution time.
It would be advantageous to be able to improve the efficiency of the decoding cycle, improve MIPS value, and decrease execution time.